package dp

// https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/
// 1比特与2比特字符
// 动态规划
// dp[n] = if bit[n] == 1 && bit[n-1] == 0 => false
//         if bit[n] == 1 && bit[n-1] == 1 => dp[n-2]
//         if bit[n] == 0 && bit[n-1] == 0 => dp[n-1]
//         if bit[n] == 0 && bit[n-1] == 1 => dp[n-1] || dp[n-2]
func IsOneBitCharacter(bits []int) bool {
	if len(bits) == 0 {
		return false
	}
	if len(bits) == 1 {
		return true
	}

	dp := make([]bool, len(bits)-1)
	for index := 0; index < len(dp); index++ {
		if index == 0 {
			if bits[0] == 0 {
				dp[0] = true
			}
		} else if index == 1 {
			if bits[1] == 1 && bits[0] == 1 {
				dp[1] = true
			} else if bits[1] == 1 && bits[0] == 0 {
				// 01
				dp[1] = false
			} else {
				// 10 or 11
				dp[1] = true
			}
		} else {
			if bits[index] == 1 && bits[index-1] == 0 {
				dp[index] = false
			} else if bits[index] == 1 && bits[index-1] == 1 {
				dp[index] = dp[index-2]
			} else if bits[index] == 0 && bits[index-1] == 0 {
				dp[index] = dp[index-1]
			} else {
				dp[index] = dp[index-1] || dp[index-2]
			}
		}
	}
	return dp[len(dp)-1]
}
